package offer.zixing.chapter08;

import java.util.HashMap;
import java.util.Map;

// 向下的路劲节点之和
public class Test50 {
    public static void main(String[] args) {
        TreeNode threeOne = new TreeNode(1);
        TreeNode threeTwo = new TreeNode(6);
        TreeNode threeThree = new TreeNode(3);
        TreeNode threeFour = new TreeNode(7);
        TreeNode twoOne = new TreeNode(2, threeOne, threeTwo);
        TreeNode twoTwo = new TreeNode(4, threeThree, threeFour);
        TreeNode root = new TreeNode(5, twoOne, twoTwo);
        System.out.println(pathSum(root, 80));
    }

    public static int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return dfs(root, 0, targetSum, map);
    }

    private static int dfs(TreeNode root, int path, int sum, Map<Integer, Integer> map) {
        if (root == null) {
            return 0;
        }
        // 累加值
        path += root.val;
        int count = map.getOrDefault(path - sum, 0);
        // 每次都都将和放入 map
        map.put(path, map.getOrDefault(path, 0) + 1);
        count += dfs(root.left, path, sum, map);
        count += dfs(root.right, path, sum, map);
        map.put(path, map.get(path) - 1);
        return count;
    }
}
